package edu.bu.cs511.p5;

import java.util.ListIterator;

/**
 * ProportionalScheduler A Proportional share scheduler based loosely
 * on the a lottery scheduling algorithm whereby one's priority
 * decreases with execution time.  Tasks can be assigned certain
 * proportions of the CPU they are to receive and the scheduler will
 * ensure that allocation will be made.  If tasks do not use 100% of
 * the CPU based on allocations, they will be assigned amounts
 * proportional to their reservations of the remainder that was
 * unallocated.  Note that this makes the algorithm work conserving.
 * <p/>
 * 
 * <p/>
 * Can remove the synchonized from the methods and attach it to datastructures
 * if there are scalability issues.
 * <p/>
 * 2/16/06, Gabriel Parmer: extended from FPScheduler 4/10/06
 */
public class ProportionalScheduler extends GenericScheduler {
    private int maxNumTokens = 100;
    private int currentActiveTokens = 0;

    /**
     * RI: maxNumTokens >= currentActiveTokens and Sum for all
     * t.totalTokens <= maxNumTokens and t.currentTokens <=
     * currentActiveTokens <p\>
     *
     * AF(c) = [t1, t2...tn] where t1 is a task in either the
     * runQueue, currentlyRunning, or the waitingQueue (see
     * super.repOk()) guaranteed t.totalTokens percent of the CPU.
     */
    public boolean repOk() {
	int active;
	int max;

	super.repOk();

	active = max = 0;
	
        if (!(maxNumTokens >= currentActiveTokens)) return false;

	for (Task cur : runQueue) {
	    max += ((PData) cur.schedData).totalTokens;
	    active += ((PData) cur.schedData).currentTokens;
	}
	for (Task cur : waitingList) {
	    max += ((PData) cur.schedData).totalTokens;
	    active += ((PData) cur.schedData).currentTokens;
	}
	for (Task cur : currentlyRunning) {
	    max += ((PData) cur.schedData).totalTokens;
	    active += ((PData) cur.schedData).currentTokens;
	}
	if (max > maxNumTokens || active > currentActiveTokens) 
	    return false;
	
        return true;
    }

    /**
     * This will be inserted into every Task scheduled by this scheduler and
     * includes the priority data needed to make scheduling decisions.
     */
    private class PData extends SchedData {
        public int totalTokens;
        public int currentTokens;

        /**
         * @REQUIRES percentCPUTime is the number of tokens for the task.
         * <p/>
         * @MODIFIES sets the number of tokens to the argument value.
         * <p/>
         * THROWS: UnsatisfiableReservationException if the requested percent of CPU
         * time cannot be accomodated.
         */
        public PData(double percentCPUTime) throws UnsatisfiableReservationException {
            super();
            int tokens;
            tokens = (int) ((double) maxNumTokens * percentCPUTime);

            if (tokens == 0) tokens = 1;

            //System.out.println(percentCPUTime +", "+ tokens + ", " +
            //(tokens+currentActiveTokens) + ", " + maxNumTokens);

            if ((tokens + currentActiveTokens) > maxNumTokens)
                throw new UnsatisfiableReservationException("Unable to satisfy reservation.");

            /* update token counts for this task */
            totalTokens = tokens;
            currentTokens = tokens;

            /*
            * increase the number of active tokens in the system
            * (ie. globally).
            */
            currentActiveTokens += tokens;

            return;
        }

	/**
	 * Forgo any tokens we might have.  This will be done when
	 * ending a task, for instance.<p/>
	 *
	 * @MODIFIES return the tokens of this task back to the pool.
	 */
	public void forfeitTokens()
	{
	    currentActiveTokens -= totalTokens;
	    totalTokens = 0;
	    currentTokens = 0;
	}

        /** @MODIFIES decriment the amount of tokens this task has. */
        public void decrimentTokens() {
            if (currentTokens > 0)
                currentTokens--;

            return;
        }

        /**
         * @MODIFIES sets the current allocated tokens to the maximum total allocated
         * tokens reserved for this task.
         */
        public void refillTokens() {
            currentTokens = totalTokens;

            return;
        }

        /**
         * @EFFECTS return the current number of remaining tokens (which
         * degrades with time) divided by the total allocated to this task.  This is
         * roughly the percent of this processes allocation still due.
         */
        public double getPercentTokensRemaining() {
            return (double) currentTokens / (double) totalTokens;
        }
    }

    /**
     * Insert a given task into the runqueue for this scheduler.  This
     * logic exists for the PorportionalScheduler as we need to insert
     * into the runqueue at a place appropriate for our current token
     * allocation (proportion left to execute) as the runqueue is
     * sorted by these tokens.<p/>
     *
     * @REQUIRES t is the task to be insert into the runQueue.
     * <p/>
     * @MODIFIES runQueue is modified in that t is added to it in a manner that
     * respects the dynamic priorities of the tasks as defined by
     * (PData)getPercentTokensRemaining().
     */
    protected void insertRunQueue(Task t) {
        ListIterator<Task> li = runQueue.listIterator(0);
        boolean insertAtEnd = true;

        //System.out.print("Inserting "+((PData)t.schedData).getPercentTokensRemaining()+": ");
        while (li.hasNext()) {
            Task cur = li.next();

            //System.out.print(((PData)cur.schedData).getPercentTokensRemaining()+ ", ");
            if (((PData) cur.schedData).getPercentTokensRemaining() <
                    ((PData) t.schedData).getPercentTokensRemaining()) {
                insertAtEnd = false;
                break;
            }
        }

        if (insertAtEnd) {
            li.add(t);
            //System.out.println("Adding task to end of runQueue.");
        } else {
            li.previous();
            li.add(t);
            //System.out.println("Adding task into the queue in the middle.");
        }

        return;
    }

    /**
     * We need to override this method from GenericScheduler so that
     * we can get a notification when a task is done executing so that
     * we can decrease the amount of tokens it has.  This is a
     * consequence of the manner in which proportionate progress is
     * ensured via tokens that decriment when tasks are executed.<p/>
     *
     * @REQUIRES t must be scheduled by this scheduler and in the
     * currentlyRunning, blocked is true if it cannot compute further at this
     * time.
     * <p/>
     * @MODIFIES if the task t is blocked, take it out of the runqueue and put
     * it in the waitingList.
     */
    synchronized public void jobFinished(Task t, boolean blocked) {
        ((PData) t.schedData).decrimentTokens();

	//System.out.println(t.getName()+" has requested concurrency of "+ t.schedData.getRequestedConcurrency());

        /**
         * If a task runs out of tokens, it is time to refill all the
         * tokens for all the tasks.
         */
        if (((PData) t.schedData).getPercentTokensRemaining() == 0) {
            //System.out.println("Refilling Tokens.");
            for (Task cur : runQueue) ((PData) cur.schedData).refillTokens();
            for (Task cur : waitingList) ((PData) cur.schedData).refillTokens();
            for (Task cur : currentlyRunning)
                ((PData) cur.schedData).refillTokens();
        }

	/* are we currently deleting? */
	if (runQueue == null) return;

        if (!runQueue.remove(t)) {
            /* must be in runningQueue */
            if (!currentlyRunning.remove(t)) {
		/* Must have been removed while running, we're done here! */
                //System.out.println("BUG in edu.bu.cs511.p5.ProportionalScheduler: finished job not in runQueue or currentlyRunning.");
		return;
            }
        }
	
        t.schedData.setAllocatedConcurrency(t.schedData.getAllocatedConcurrency() - 1);

        if (blocked) {
            waitingList.add(t);
        } else {
            addToRunqueue(t);
        }
	
    }

    /**
     * Constructor to create a default proportional share scheduler.
     * <p/>
     * @REQUIRES none
     */
    public ProportionalScheduler() {
        super();
    }

    /**
     * Constructor to create a proportional share scheduler with a
     * defined maximum concurrency level (maximum number of threads it
     * will every ask for).<p/>
     *
     * @REQUIRES maxConcurr is the maximum value for the concurrency
     * supported by this scheduler, or the maximum number of threads it will
     * pass to children.
     */
    public ProportionalScheduler(int maxConcurr) {
        super(maxConcurr);
    }

    /**
     * Add a new task to this scheduler's structures.  Specify a
     * proportion that task is to have.<p/>
     *
     * @REQUIRES t is the task to add and s is a string representation
     * of the proportion of the (virtual) CPU to allocate to this
     * task.  s is a string that must be formattable to a double in
     * [0, 1] which represents the proportion of the CPU ensured..  A
     * task with proportion of 0 will be serviced best effort. <p/>
     *
     * @MODIFIES adds the task to the waitingList of this scheduler and sets its
     * priority to be an integer designated by the String s.
     *
     * @EFFECTS returns true.
     */
    synchronized public boolean addTask(Task t, String s) {
        double proportion;

        /* Not on a fast path, so this should be acceptable. */
        try {
            proportion = Double.parseDouble(s);
        } catch (NumberFormatException nfe) {
            proportion = 0;
        }

        if (proportion > 1) proportion = 1;
        if (proportion < 0) proportion = 0;

        try {
            t.schedData = new PData(proportion);
        } catch (UnsatisfiableReservationException ure) {
            return false;
        }

        //System.out.println("Adding Task with proportion "+proportion);

        waitingList.add(t);

        return true;
    }

    /**
     * Add a new task to this scheduler's structures.  <p/>
     *
     * @MODIFIES add the task t to the waitingList of this scheduler.
     * <p/>
     * @REQUIRES t is a Task that is not a ThreadManager
     * <p/>
     * @EFFECTS returns true
     */
    synchronized public boolean addTask(Task t) {
        return addTask(t, "0");
    }

    /**
     * Remove a given task from the scheduler's structures.  If the
     * task is not in any of the queues, then a bug report is emitted.<p/>
     *
     * @REQUIRES task t must be in either the runQueue, the
     * waitingList, or the currentlyRunning for this scheduler.
     *
     * <p/>
     * @MODIFIES remove the task t from the runQueue or the waitingList.
     */
    synchronized public void removeTask(Task t) {
	super.removeTask(t);

	((PData)t.schedData).forfeitTokens();
    }

}
